package io.zhengsh.vvip.leetcode.q100;

import io.zhengsh.vvip.leetcode.ListNode;

public class Question19 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);

        ListNode listNode = solution.removeNthFromEnd(node, 2);
        System.out.println(listNode);

    }


    static class Solution {
        /**
         * 采用双指针的方式
         *
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            ListNode first = head;
            ListNode second = dummy;
            // 快指针先走 N 步
            for (int i = 0; i < n; ++i) {
                first = first.next;
            }
            // 快指针走到终点，慢指针恰好处于 length - n 位置
            while (first != null) {
                first = first.next;
                second = second.next;
            }
            // 跳过第 N 个节点
            second.next = second.next.next;
            return dummy.next;
        }
    }
}
